List edge and list total colorings of planar graphs without 6-cycles with chord (Q2880475)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: List edge and list total colorings of planar graphs without 6-cycles with chord |
scientific article; zbMATH DE number 6023965
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | List edge and list total colorings of planar graphs without 6-cycles with chord |
scientific article; zbMATH DE number 6023965 |
Statements
13 April 2012
0 references
list coloring
0 references
list edge coloring
0 references
list total coloring
0 references
planar graph
0 references
choosability
0 references
List edge and list total colorings of planar graphs without 6-cycles with chord (English)
0 references
The author proves the following two results related to list edge and list total colorings of planar graphs without 6-cycles with chord.NEWLINENEWLINELemma: Let \(G\) be a critical planar graph without 6-cycles with chord. If \(\Delta(G) \geq 6\), then there is an edge \(uv \in E(G)\) such that \(\min\{ d(u), d(v)\} \leq \lfloor \frac{\Delta(G) + 1}{2} \rfloor\) and \(d(u) + d(v) \leq \max\{8, \Delta(G) + 2\}\).NEWLINENEWLINETheorem: If \(G\) is a planar graph without 6-cycles with chord, then \(\chi_{1}^{'}(G) \leq \Delta(G) + 1\) and \(\chi_{1}^{''}(G) \leq \Delta(G) + 2\), where \(\Delta(G) \geq 6\), (where \(\chi_{1}^{'}(G)\) denotes the list edge coloring number of \(G\) and \(\chi_{1}^{''}(G)\) denotes the list total coloring number of \(G\)).NEWLINENEWLINEThis gives a partial answer to the List Coloring Conjecture in the case of a planar graph \(G\) without 6-cycles with chord,NEWLINENEWLINE Conjecture: For a multigraph \(G\),NEWLINE{\parindent=7mmNEWLINE\begin{itemize}\item[(a)]\(\chi_{1}^{'}(G) = \chi^{'}(G)\); NEWLINE\item[(b)]\(\chi_{1}^{''}(G) = \chi^{''}(G)\).NEWLINENEWLINENEWLINE\end{itemize}}
0 references
0.8923470973968506
0 references
0.8676760196685791
0 references
0.8626367449760437
0 references
0.8589931726455688
0 references
0.8516619205474854
0 references