Let $G$ be an $n$-vertex graph and let $L:V(G)rightarrow P({1,2,3})$ be a list assignment over the vertices of $G$, where each vertex with list of size 3 and of degree at most 5 has at least three neighbors with lists of size 2. We can determine $L$-
choosability of $G$ in $O(1.3196^{n_3+.5n_2})$ time, where $n_i$ is the number of vertices in $G$ with list of size $i$ for $iin {2,3}$. As a corollary, we conclude that the 3-colorability of any graph $G$ with minimum degree at least 6 can be determined in $O(1.3196^{n-.5Delta(G)})$ time.
Let $f$ be an optimal proper coloring of a graph $G$ and let $c$ be a coloring of the vertices of $G$ obtained by permuting the colors on vertices in the proper coloring $f$. The villainy of $c$, written $B(c)$, is the minimum number of vertices that
must be recolored to obtain a proper coloring of $G$ with the additional condition that the number of times each color is used does not change. The villainy of $G$ is defined as $B(G)=max_{c}B(c)$, over all optimal proper colorings of $G$. In this paper, we characterize graphs $G$ with $B(G)=2$.
Let $G$ be an $n$-vertex graph with the maximum degree $Delta$ and the minimum degree $delta$. We give algorithms with complexity $O(1.3158^{n-0.7~Delta(G)})$ and $O(1.32^{n-0.73~Delta(G)})$ that determines if $G$ is 3-colorable, when $delta(G)geq 8$ and $delta(G)geq 7$, respectively.
The distinguishing number of a graph $G$, denoted $D(G)$, is the minimum number of colors needed to produce a coloring of the vertices of $G$ so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment $L$ on a g
raph $G$ is a function that assigns each vertex of $G$ a set of colors. An $L$-coloring of $G$ is a coloring in which each vertex is colored with a color from $L(v)$. The list distinguishing number of $G$, denoted $D_{ell}(G)$ is the minimum $k$ such that every list assignment $L$ that assigns a list of size at least $k$ to every vertex permits a distinguishing $L$-coloring. In this paper, we prove that when and $n$ is large enough, the distinguishing and list-distinguishing numbers of $K_nBox K_m$ agree for almost all $m>n$, and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to the graph distinguishing problem and also prove an inequality for the binomial distribution that may be of independent interest.
Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most $3$ is $7$-colorable. We prove this conjecture using the discharging method and computational techniques to verify reducible configurations.
A graph $G$ is $k$-$weighted-list-antimagic$ if for any vertex weighting $omegacolon V(G)tomathbb{R}$ and any list assignment $Lcolon E(G)to2^{mathbb{R}}$ with $|L(e)|geq |E(G)|+k$ there exists an edge labeling $f$ such that $f(e)in L(e)$ for all $ei
n E(G)$, labels of edges are pairwise distinct, and the sum of the labels on edges incident to a vertex plus the weight of that vertex is distinct from the sum at every other vertex. In this paper we prove that every graph on $n$ vertices having no $K_1$ or $K_2$ component is $lfloor{frac{4n}{3}}rfloor$-weighted-list-antimagic. An oriented graph $G$ is $k$-$oriented-antimagic$ if there exists an injective edge labeling from $E(G)$ into ${1,dotsc,|E(G)|+k}$ such that the sum of the labels on edges incident to and oriented toward a vertex minus the sum of the labels on edges incident to and oriented away from that vertex is distinct from the difference of sums at every other vertex. We prove that every graph on $n$ vertices with no $K_1$ component admits an orientation that is $lfloor{frac{2n}{3}}rfloor$-oriented-antimagic.
We apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to the
m, and the structure theorems and reducibility results are of independent interest.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
