DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

J.A. Mudrock, M. Marsh, T. Wagstrom

Title:

On list equitable total colorings of the generalized theta graph

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-08-02, Revised: 2019-12-07, Accepted: 2019-12-10, https://doi.org/10.7151/dmgt.2292

Abstract:

In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A $k$-assignment, $L$, for a graph $G$ assigns a list, $L(v)$, of $k$ available colors to each $v \in V(G)$, and an equitable $L$-coloring of $G$ is a proper coloring, $f$, of $G$ such that $f(v) \in L(v)$ for each $v \in V(G)$ and each color class of $f$ has size at most $\lceil |V(G)|/k \rceil$. Graph $G$ is equitably $k$-choosable if $G$ is equitably $L$-colorable whenever $L$ is a $k$-assignment for $G$. In 2018, Kaul, Mudrock, and Pelsmajer subsequently introduced the List Equitable Total Coloring Conjecture which states that if $T$ is a total graph of some simple graph, then $T$ is equitably $k$-choosable for each $k \geq \max \{\chi_\ell(T), \Delta(T)/2 + 2 \}$ where $\Delta(T)$ is the maximum degree of a vertex in $T$ and $\chi_\ell(T)$ is the list chromatic number of $T$. In this paper, we verify the List Equitable Total Coloring Conjecture for subdivisions of stars and the generalized theta graph.

Keywords:

graph coloring, total coloring, equitable coloring, list coloring, equitable choosability

PDF
Close