An Infinite Family of Sum-Paint Critical Graphs
- PDF / 425,597 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 16 Downloads / 200 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
An Infinite Family of Sum-Paint Critical Graphs Thomas Mahoney1
•
Chad Wiley1
Received: 17 July 2019 / Revised: 4 June 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Independently, Zhu and Schauz introduced online list coloring in 2009. In each round, a set of vertices allowed to receive a particular color is marked, and the coloring algorithm (Painter) gives a new color to an independent subset of these vertices. A graph G is f-paintable for a function f : VðGÞ ! N if Painter can produce a proper coloring when the number of times each vertex v is allowed to be marked is f(v). In 2002, Isaak introduced sum list coloring and the resulting parameter called sum-choosability.PThe analogous parameter sum-paintability, denoted s ch, is the minimum of f ðvÞ over all functions f such that G is fpaintable. Always s chðGÞ jVðGÞj þ jEðGÞj, and we say that G is sp-greedy when equality holds. When a graph fails to be sp-greedy, any graph containing it as an induced subgraph also fails to be sp-greedy. A graph is sp-critical when it is not spgreedy but all of its proper induced subgraphs are sp-greedy. We prove the existence of an infinite family of sp-critical graphs. As a corollary, we prove that neither spgreedy, nor sc-greedy, graphs can be characterized by forbidding a finite family of induced subgraphs. Keywords Sum paintability Sum choosability Online list coloring
Mathematics Subject Classification 05C10
& Thomas Mahoney [email protected] Chad Wiley [email protected] 1
Emporia State University, Emporia, KS, USA
123
Graphs and Combinatorics
1 Introduction Vizing [11] and independently Erd}os et al. [4] introduced a list version of graph coloring in which each vertex v is assigned a set L(v) (called its list) of available colors. An L-coloring is a proper coloring / such that /ðvÞ 2 LðvÞ for each vertex v. A graph G is f-choosable if an L-coloring exists whenever jLðvÞj f ðvÞ for each vertex v. Seeking to minimize the total number of list elements needed, Isaak introduced P sum-choosability [6, 7]. The sum-choice number, denoted schðGÞ, is the least f ðvÞ over all f such that G is f-choosable. By utilizing a greedy coloring strategy, he observed that always schðGÞ jVðGÞj þ jEðGÞj; graphs achieving equality in this bound are sum-choice greedy, which we abbreviate to sc-greedy. Schauz [9] introduced an online version of choosability, and in the same year, Zhu [12] gave an equivalent definition. Given a list assignment with colors from N, suppose that on round i, the coloring algorithm must decide which vertices will receive color i without knowing which colors will appear in later rounds of the game. Since sets of vertices receiving a particular color are revealed one at a time, the coloring algorithm cannot see the full lists and thus has less information than in the standard list coloring problem. Hence, producing a proper coloring is more difficult. We define and study the Lister/Painter game to model the worst-case sce
Data Loading...
