Source author record

Carl Johan Casselgren

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Single conflict coloring and palette sparsification of uniform hypergraphs

We introduce and investigate single conflict coloring in the setting of r-uniform hypergraphs. We establish some basic properties of this hypergraph coloring model and study a probabilistic model of single conflict coloring where the conflicts for each edge are chosen randomly; in particular, we prove a sharp threshold-type result for complete graphs and establish a sufficient condition for single conflict colorability of r-uniform hypergraphs in this model. Furthermore, we obtain a related palette sparsification-type result for general list coloring of linear uniform hypergraphs (i.e. uniform hypergraphs where any two edges share at most one common vertex). Throughout the paper we pose several questions and conjectures

preprint2020arXiv

Completing partial Latin squares with two filled rows and three filled columns

Consider a partial Latin square $P$ where the first two rows and first three columns are completely filled, and every other cell of $P$ is empty. It has been conjectured that all such partial Latin squares of order at least $8$ are completable. Based on a technique by Kuhl and McGinn we describe a framework for completing partial Latin squares in this class. Moreover, we use our method for proving that all partial Latin squares from this family, where the intersection of the nonempty rows and columns form a Latin rectangle with three distinct symbols, is completable.

preprint2020arXiv

Improper interval edge colorings of graphs

A $k$ -improper edge coloring of a graph $G$ is a mapping $α:E(G)\longrightarrow \mathbb{N}$ such that at most $k$ edges of $G$ with a common endpoint have the same color. An improper edge coloring of a graph $G$ is called an improper interval edge coloring if the colors of the edges incident to each vertex of $G$ form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph $G$ defined as the smallest $k$ such that $G$ has a $k$ -improper interval edge coloring; we denote the smallest such $k$ by $μ_{\mathrm{int}}(G)$ . We prove upper bounds on $μ_{\mathrm{int}}(G)$ for general graphs $G$ and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine $μ_{\mathrm{int}}(G)$ exactly for $G$ belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer $k$ , there exists a graph $G$ with $μ_{\mathrm{int}}(G) =k$ . Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring.

preprint2017arXiv

Coloring graphs of various maximum degree from random lists

Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $Δ=Δ(n)$ . Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$ -subsets of a color set $\mathcal{C}$ of size $σ= σ(n)$ . Such a list assignment is called a \emph{random $(k,\mathcal{C})$ -list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$ ) of the existence of a proper coloring $φ$ of $G$ , such that $φ(v) \in L(v)$ for every vertex $v$ of $G$ , a so-called $L$ -coloring. We give various lower bounds on $σ$ , in terms of $n$ , $k$ and $Δ$ , which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$ -coloring of $G$ . In particular, we show, for all fixed $k$ and growing $n$ , that if $σ(n) = ω(n^{1/k^2} Δ^{1/k})$ and $Δ=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$ , then the probability that $G$ has an $L$ -coloring tends to 1 as $n \rightarrow \infty$ . If $k\geq 2$ and $Δ= Ω(n^{1/2})$ , then the same conclusion holds provided that $σ=ω(Δ)$ . We also give related results for other bounds on $Δ$ , when $k$ is constant or a strictly increasing function of $n$ .

preprint2016arXiv

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An \emph{interval $t$ -coloring} of a multigraph $G$ is a proper edge coloring with colors $1,\dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors. A \emph{cyclic interval $t$ -coloring} of a multigraph $G$ is a proper edge coloring with colors $1,\dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$ . Denote by $w(G)$ ( $w_{c}(G)$ ) and $W(G)$ ( $W_{c}(G)$ ) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$ , respectively. We present some new sharp bounds on $w(G)$ and $W(G)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$ -connected multigraph with an interval coloring, then $W(G)\leq 1+\left\lfloor \frac{|V(G)|}{2}\right\rfloor(Δ(G)-1)$ . We also give several results towards the general conjecture that $W_{c}(G)\leq |V(G)|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$ .

preprint2014arXiv

Solution of Vizing's Problem on Interchanges for Graphs with Maximum Degree 4 and Related Results

Let $G$ be a Class 1 graph with maximum degree $4$ and let $t\geq 5$ be an integer. We show that any proper $t$ -edge coloring of $G$ can be transformed to any proper $4$ -edge coloring of $G$ using only transformations on $2$ -colored subgraphs (so-called interchanges). This settles the smallest previously unsolved case of a well-known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper $5$ -edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7-edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.