Sufficient conditions for a planar graph to be list edge \(\Delta \)-colorable and list totally \((\Delta +1)\)-colorable (Q1939571): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
m rollbackEdits.php mass rollback Tag: Rollback |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2012.11.026 / rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2037250996 / rank | |||
Revision as of 17:37, 21 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sufficient conditions for a planar graph to be list edge \(\Delta \)-colorable and list totally \((\Delta +1)\)-colorable |
scientific article |
Statements
Sufficient conditions for a planar graph to be list edge \(\Delta \)-colorable and list totally \((\Delta +1)\)-colorable (English)
0 references
4 March 2013
0 references
The list chromatic index of a graph \(G\), \(\chi'_l(G)\), is the smallest integer \(l\) such that given any family of sets (lists) of colors \(L(x)\) assigned to the edges of \(G\) where \(|L(x)| \leq l\) for \(x\in E(G)\), it is possible to choose a color from every list resulting in proper edge-coloring of \(G\). Similarly, the list total chromatic number of \(G\), \(\chi''_l(G)\), is the smallest integer \(l\) such that given any family of sets (lists) of colors \(L(x)\) assigned to the edges and vertices of \(G\) where \(|L(x)| \leq l\) for \(x\in V(G) \cup E(G)\), it is possible to choose a color from every list resulting in such a coloring that each pair of adjacent or incident elements of \(V(G)\cup E(G)\) obtains distinct colors. The authors prove that \(\chi'_l = \Delta(G)\) and \(\chi''_l(G) = \Delta(G)+1\) for the planar graphs with the maximum degree \(\Delta(G) \geq 7\) (\(\Delta(G) \geq 8\), respectively) and not containing adjacent cycles of length \(4\) (\(3\) and \(5\), respectively).They also prove that \(\chi'_l(G) \leq \Delta(G)+1\) and \(\chi''_l(G) \leq \Delta(G)+2\) if \(\Delta(G) \geq 6\) and there are no adjacent cycles of length \(3\) and \(5\) in \(G\).
0 references
Planar graph
0 references
list edge coloring
0 references
list total coloring
0 references
list chromatic index
0 references
cycle
0 references
maximum degree
0 references