Discrete Mathematics and Combinatorics Commons^™

From Total Domination To Graph Coloring, Sawyer Isaac Osborn

Dissertations

A question involving a chess piece called a prince on the 8×8 chessboard leads to a concept in graph theory involving total domination. We say a vertex u in a graph G totally dominates a vertex v if u is adjacent to v. A subset S of the vertex set of a graph G is a total dominating set for G if every vertex in G is totally dominated by at least one vertex of S. If S is a total dominating set of G, then σ_S(v) denotes the number of …

Dominating Hadwiger's Conjecture For 2k2-Free Graphs, Thomas Tibbetts

Honors Undergraduate Theses

A dominating K_t minor in a graph �� is a sequence (��₁,…,��_t) of pairwise disjoint non-empty connected subgraphs of ��, such that for 1≤��< ��≤��, every vertex in ��_j has a neighbor in ��_i. Replacing “every vertex in ��_j” by “some vertex in ��_j” retrieves the standard definition of a ��_t minor. The strengthened notion was introduced by Illingworth and Wood in 2024, who asked whether every graph with chromatic number �� contains a dominating ��_t minor. This is a substantial strengthening of the celebrated Hadwiger’s Conjecture, which asserts that every …

Coloring Trivalent Graphs: A Defect Tft Approach, Amit Kumar

LSU Doctoral Dissertations

We show that the combinatorial matter of graph coloring is, in fact, quantum in the sense of satisfying the sum over all the possible intermediate state properties of a path integral. In our case, the topological field theory (TFT) with defects gives meaning to it. This TFT has the property that when evaluated on a planar trivalent graph, it provides the number of Tait-Coloring of it. Defects can be considered as a generalization of groups. With the Klein-four group as a 1-defect condition, we reinterpret graph coloring as sections of a certain bundle, distinguishing a coloring (global-sections) from a coloring …

Optimal Network Analysis Through Vertex Order Coloring Of Intuitionistic Fuzzy Graph Operations, A. Meenakshi, S. Dhanushiya, Hong Qin, Maniyandy Elangovan

Data Science Faculty Publications

Intuitionistic fuzzy graphs IFGs are a powerful tool for modeling uncertainty and complex relationships. They offer versatile frameworks for addressing real-world challenges. In this research, we have introduced intuitionistic fuzzy vertex order coloring IFVOC and analyzed the alpha-strong (alpha str), beta-strong (beta str), and gamma-strong (gamma str) vertices through their degree. We explored important theorems based on the types of strong vertices, broadening the scope of our study. We analyzed multiple IFG products to determine the most optimal network based on some important metrics, including the weight and total number of alpha str vertices, the chromatic number, and the weight …

Graph Coloring Reconfiguration, Reem Mahmoud

Theses and Dissertations

Reconfiguration is the concept of moving between different solutions to a problem by transforming one solution into another using some prescribed transformation rule (move). Given two solutions s₁ and s₂ of a problem, reconfiguration asks whether there exists a sequence of moves which transforms s₁ into s₂. Reconfiguration is an area of research with many contributions towards various fields such as mathematics and computer science.
The k-coloring reconfiguration problem asks whether there exists a sequence of moves which transforms one k-coloring of a graph G into another. A move in this case is a type …

Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver

Rose-Hulman Undergraduate Mathematics Journal

This paper utilizes heuristic algorithms for determining graph thickness in order to attempt to find a 10-chromatic thickness-2 graph. Doing so would eliminate 9 colors as a potential solution to the Earth-moon Problem. An empirical analysis of the algorithms made by the author are provided. Additionally, the paper lists various graphs that may or nearly have a thickness of 2, which may be solutions if one can find two planar subgraphs that partition all of the graph’s edges.

Selected Problems In Graph Coloring, Hudson Lafayette

Theses and Dissertations

The Borodin–Kostochka Conjecture states that for a graph G, if ∆(G) ≥ 9 and ω(G) ≤ ∆(G) − 1, then χ(G) ≤ ∆(G) − 1. We prove the Borodin–Kostochka Conjecture for (P5, gem)-free graphs, i.e., graphs with no induced P5 and no induced K1 ∨P4.

For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a function f : V (G) → [k] such that |f(v) ∩f (w)| < d(v,w) for all distinct v, w ∈ V(G). The t-tone chromatic number of G, denoted τt(G), is the minimum k such that G is t-tone k-colorable. For small values of t, we prove sharp or nearly sharp upper bounds on the t-tone chromatic number of various classes of sparse graphs. In particular, we determine τ2(G) exactly when mad(G) < 12/5 and also determine τ2(G), up to a small additive constant, when G is outerplanar. Finally, we determine τt(Cn) exactly when t ∈ {3, 4, 5}.

Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi

HMC Senior Theses

In the first half of this thesis, we explore the polynomial-time hierarchy, emphasizing an intuitive perspective that associates decision problems in the polynomial hierarchy to combinatorial games with fixed numbers of turns. Specifically, problems in �� are thought of as 0-turn games, ���� as 1-turn “puzzle” games, and in general ��ₖ�� as ��-turn games, in which decision problems answer the binary question, “can the starting player guarantee a win?” We introduce the formalisms of the polynomial hierarchy through this perspective, alongside definitions of ��-turn CIRCUIT SATISFIABILITY games, whose ��ₖ��-completeness is assumed from prior work (we briefly justify this assumption …

Extremal Problems On Induced Graph Colorings, James Hallas

Dissertations

Graph coloring is one of the most popular areas of graph theory, no doubt due to its many fascinating problems and applications to modern society, as well as the sheer mathematical beauty of the subject. As far back as 1880, in an attempt to solve the famous Four Color Problem, there have been numerous examples of certain types of graph colorings that have generated other graph colorings of interest. These types of colorings only gained momentum a century later, however, when in the 1980s, edge colorings were studied that led to vertex colorings of various types, led by the introduction …

3-Maps And Their Generalizations, Kevin J. Mccall

Theses and Dissertations

A 3-map is a 3-region colorable map. They have been studied by Craft and White in their paper 3-maps. This thesis introduces topological graph theory and then investigates 3-maps in detail, including examples, special types of 3-maps, the use of 3-maps to find the genus of special graphs, and a generalization known as n-maps.

An Exploration Of The Chromatic Polynomial, Amanda Aydelotte

Mathematics Undergraduate Theses

In 1912, George Birkhoff was studying the Four Color Problem, and in doing so introduced the concept of the chromatic polynomial. While this did not end up directly contributing to proving that every map could be colored with four colors such that no region shares a border with another region of the same color, the chromatic polynomial has been found to have some very interesting properties. In this paper, it will be our goal to examine some of these properties and use them to determine information about their corresponding graphs.

A Beautiful Proof By Induction, Lars-Daniel Öhman

Journal of Humanistic Mathematics

The purpose of this note is to present an example of a proof by induction that in the opinion of the present author has great aesthetic value. The proof in question is Thomassen's proof that planar graphs are 5-choosable. I give a self-contained presentation of this result and its proof, and a personal account of why I think this proof is beautiful.

A secondary purpose is to more widely publicize this gem, and hopefully make it part of a standard set of examples for examining characteristics of proofs by induction.

Reed's Conjecture And Cycle-Power Graphs, Alexa Serrato

HMC Senior Theses

Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.