Zobrazeno 1 - 10
of 109
pro vyhledávání: '"05C15, 05C25"'
In the past, analogies to Brooks' theorem have been found for various parameters of graph coloring for infinite locally finite connected graphs in ZFC. We prove these theorems are not provable in ZF (i.e. the Zermelo-Fraenkel set theory without the A
Externí odkaz:
http://arxiv.org/abs/2408.00812
We prove analogs of Brooks' Theorem for the list-distinguishing chromatic number of finite connected graphs. Moreover, we give new examples to determine two sharp upper bounds for the list-distinguishing chromatic number of a graph G in terms of the
Externí odkaz:
http://arxiv.org/abs/2405.12733
Autor:
S, Prajnanaswaroopa
In this paper, we try to determine exact or bounds on the choosability, or list chromatic numbers of some Cayley graphs, typically some Unitary Cayley graphs and Cayley graphs on Dihedral groups.
Comment: 3 pages, short paper
Comment: 3 pages, short paper
Externí odkaz:
http://arxiv.org/abs/2402.16047
Autor:
Mifsud, Xandru
We give results concerning two problems on the recently introduced flip colourings of graphs, a new class of local v. global phenomena. We prove that for $(b, r)$-flip sequences with $4 \leq b < r < b + 2 \left\lfloor\frac{b+2}{6}\right\rfloor^2$, sm
Externí odkaz:
http://arxiv.org/abs/2401.02315
Autor:
Cockburn, Sally, Klivans, Max
Praeger-Xu graphs are connected, symmetric, 4-regular graphs that are unusual both in that their automorphism groups are large, and in that vertex stabilizer subgroups are also large. Determining number and distinguishing number are parameters that m
Externí odkaz:
http://arxiv.org/abs/2309.11474
Stanley's Tree Isomorphism Conjecture posits that the chromatic symmetric function can distinguish non-isomorphic trees. While already established for caterpillars and other subclasses of trees, we prove the conjecture's validity for a new class of t
Externí odkaz:
http://arxiv.org/abs/2307.02234
Autor:
Kwaśny, Jakub, Stawiski, Marcin
We say that an edge colouring breaks an automorphism if some edge is mapped to an edge of a different colour. We say that the colouring is distinguishing if it breaks every non-identity automorphism. We show that such colouring can be chosen from any
Externí odkaz:
http://arxiv.org/abs/2306.06418
A set $D$ of vertices is a strong dominating set in a graph $G$, if for every vertex $x\in V(G) \setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $deg(x) \leq deg(y)$. The strong domination number $\gamma_{st}(G)$ of $G$ is the minimum ca
Externí odkaz:
http://arxiv.org/abs/2306.01608
Autor:
S, Prajnanaswaroopa
Cayley graphs are graphs on algebraic structures, typically groups or group-like structures. In this paper, we have obtained a few results on Cayley graphs on Cyclic groups, powers of cycles, Cayley graphs on some non-abelian groups, and vertex, edge
Externí odkaz:
http://arxiv.org/abs/2305.11623
Autor:
Ghanbari, Nima, Alikhani, Saeid
Let $G=(V,E)$ be a simple graph. A set $D\subseteq V$ is a strong dominating set of $G$, if for every vertex $x\in V\setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $deg(x)\leq deg(y)$. The strong domination number $\gamma_{st}(G)$ is de
Externí odkaz:
http://arxiv.org/abs/2302.01126